package sort;

import java.util.Scanner;
import java.util.Arrays;
/**
 * @ClassName: shell
 * @Auther: Drawin
 * @Date: 2021/9/20 22:03
 * @Description:
 */


public class shell {
    public static void main(String[] args) {
        System.out.println("请输入数组的个数：");
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        int[] a= new int[n];
        for(int i=0;i<a.length;i++){
            a[i]=s.nextInt();
        }

        for(int i=n/2;i>0;i/=2)
            for(int j=i;j<n;j++){
                int temp=a[j];
                int k=0;
                for(k=j-i;k>=0;k-=i){
                    if(temp<a[k]){
                        a[k+i]=a[k];
                    }else{
                        break;
                    }
                }
                a[k+i]=temp;
            }
        System.out.println(Arrays.toString(a));
    }
}
